<!--
 * @Descripttion: 
 * @version: 
 * @Author: 尹鹏孝
 * @Date: 2021-12-27 09:49:03
 * @LastEditors: 尹鹏孝
 * @LastEditTime: 2021-12-27 10:37:06
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>中序，后序数组求完整二叉树</title>
</head>

<body>
    <script>
        // 中序遍历 inorder = [9, 3, 15, 20, 7] 后序遍历 postorder = [9, 15, 7, 20, 3] 返回如下的二叉树：
        // 思路
        // 首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来在切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
        // 具体切割方法
        // 1、如果数组是空就返回空节点
        // 2、如果不为空，取后序数组的最后一个元素作为切割点
        // 3、找到后序数组的最后一个元素作在中序中的位置，作为切割点
        // 4、切割中序数组，切成中序左数组和中序右数组（顺序别搞反，一定是先切割中序数组）
        // 5、切割后序数组，切成后序左数组和后序右数组
        // 6、递归处理左区间和右区间
        // 注意：难点是切割顺序执行。和变量的设置
        // 坚持循环不变量的重要性：环不变量的重要性，在二分查找以及螺旋矩阵的求解中，坚持循环不变量非常重要，循环不变量指的是？
        // 答：是左闭右开，还有左开右闭，还是左闭右闭，这个就是不变量，要在递归中保持这个不变量
        // 中序和后序，前序都可以确定二叉树那么前序后序可以确定二叉树吗
        // 不能，因为没有中序确定左右不分就无法分割。左序：中左右，后序左中右，无法确定顺序，不能切割
        var buildTree = function (inOrder, postOrder) {
            if (!postOrder.length) {
                return null;
            }
            const rootVal = postOrder.pop();
            let rootIndex = inOrder.indexOf(rootVal);
            const root = new TreeNode(rootVal);
            root.left = buildTree(inOrder.slice(0, rootIndex), postOrder.slice(0, rootIndex))
            root.right = buildTree(inOrder.slice(rootIndex + 1), postOrder.slice(rootIndex))
        }


        // 从前序和中序遍历二叉树得到二叉树
        var buildTree = function (preOrder, inOrder) {
            if (!preOrder.length) {
                return null;
            }
            const rootVal = preOrder.shift();
            const index = inOrder.indexOf(rootVal);
            const root = new NodeTree(rootVal);
            root.left = buildTree(preOrder.slice(0, index), inOrder.slice(0, index));
            root.right = buildTree(preOrder.slice(index), inOrder.slice(index));

        }




    </script>

</body>

</html>